package leetcode.code2002;

import leetcode.helper.MaxDebug;

/**
 *
 * @author CaoYu
 * @date 2021年12月5日
 * @description
 */
public class Solution extends S2002 {

	private int range;
	private int len;
	private int max;

	@Override
	public int maxProduct(String s) {
		len = s.length();
		int n = 1 << len;
		range = n - 1;
		max = 0;
		boolean[] dp = new boolean[n];
		char[] s1 = new char[len];
		char[] s2 = new char[len];
		this.f(s.toCharArray(), 0, s1, 0, s2, 0, 0, dp);
		return max;
	}

	private void f(char[] charArray, int index, char[] s1, int p1, char[] s2, int p2, int num, boolean[] dp) {
		if (index == len) {
			int len1 = this.longestPalindromeSubseq(s1, p1);
			int len2 = this.longestPalindromeSubseq(s2, p2);
			int ans = len1 * len2;
			max = Math.max(ans, max);
			dp[num] = true;
			dp[num ^ range] = true;
			return;
		}
		char c = charArray[index];
		s2[p2] = c;
		this.f(charArray, index + 1, s1, p1, s2, p2 + 1, num, dp);
		num = num | 1 << (len - index - 1);
		if (!dp[num]) {
			s1[p1] = c;
			this.f(charArray, index + 1, s1, p1 + 1, s2, p2, num, dp);
		}
	}

	public int longestPalindromeSubseq(char[] chars, int Len) {
		if (Len == 0)
			return 0;
		int[][] dp = new int[Len][Len];
		for (int i = Len - 1; i >= 0; i--) {
			dp[i][i] = 1;
			for (int j = i + 1; j < Len; j++) {
				dp[i][j] = chars[i] == chars[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
		return dp[0][Len - 1];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		so.debug4();
		so.debug3();
		MaxDebug.debug14(so);
	}

}
